package com.chen.leet_code.answer

import android.icu.number.IntegerWidth
import java.security.SecureRandom
import kotlin.random.Random

/**
 * 实现一个数据结构，保证数据的插入删除都是 o（1）时间复杂度
 */
class RandomizedSet {

    val datas :ArrayList<Int> = ArrayList<Int>()
    val indesDatas :HashMap<Int,Int> = HashMap()
    val random :SecureRandom = SecureRandom()

    fun insert(a: Int): Boolean {
        if(indesDatas.containsKey(a)){
            return false
        }else{
            datas.add(a)
            indesDatas[a] = datas.size-1
            return true
        }
    }

    fun remove(`val`: Int): Boolean {
        if (!indesDatas.contains(`val`)) {
            return false
        }
        val index = indesDatas.remove(`val`) ?: return false
        val last = datas[datas.size - 1]
        datas[index] = last
        if (index != datas.size -1){
            indesDatas[last] = index
        }
        datas.removeAt(datas.size - 1)
        return true


    }

    fun getRandom(): Int {

       val pos = random.nextInt(datas.size)
        println(" size:${datas.size}, pos:$pos")
        return datas.get(pos)
    }
}